/*
**  File: Glist.c
**
**  Code for a general list abstraction, as described in:
**  "ANSI C Problem-solving and Programming", K. A. Barclay, 
**  Prentice Hall,  1990, p. 393-399.
**
**  Notes:
**  - head is a sentinel: it delimits the boundary in an otherwise
**    circularly linked list
**  - the traverse and find operations stop at the head; 
**  - isinlist returns false if at the head,  so it can be used to test
**    for the success of a find operation
**
*/

#include <stdio.h>
#include <stdlib.h>

#include "General.h"

/* BEGIN_EXTH */
#include "GlistTypes.h"
/* END_EXTH */

#define LENGTH  ((List *)list)->length
#define HEAD    ((List *)list)->head
#define CURSOR  ((List *)list)->cursor

typedef struct list   List;
typedef struct node   Node;

struct list
{
    int    length;
    Node   *head;
    Node   *cursor;
};

struct node
{
    GType  data;
    Node   *predecessor;
    Node   *successor;
};

static void error( char *mess )
{
    fprintf( stderr, "%s\n", mess );
    exit( 1 );
}

/****************  function prototypes  ****************/

#include "Glist.h"

/* BEGIN_EXTH */

GList gempty( void )
{
    List   *list = NEW( List, 1 );
    Node   *node = NEW( Node, 1 );
    
#ifdef DEBUG
puts( "in gempty" );
#endif
    if ( list == NULL || node == NULL ) error( "in gempty: No space" );
    node->data = NULL;
    node->predecessor = node->successor = node;
    list->length = 0;
    list->head = list->cursor = node;
#ifdef DEBUG
printf( "cursor: %p\n", CURSOR );
#endif
    return list;
}

int glength( GList list )
{
    return LENGTH;
}

Boolean gisempty( GList list )
{
    return ( LENGTH == 0 ) ? true : false;
}

Boolean gisinlist( GList list )
{
    return ( HEAD == CURSOR ) ? false : true;
}

GType gcontent( GList list )
{
    if ( HEAD == CURSOR ) error( "in gcontent: Access violation" );
    return CURSOR->data;
}

GList gsethead( GList list )
{
#ifdef DEBUG
puts( "in sethead" );
#endif
    CURSOR = HEAD->successor;
#ifdef DEBUG
printf( "cursor now at: %s %p\n", CURSOR->data, CURSOR );
#endif
    return list;
}

GList gsettail( GList list )
{
#ifdef DEBUG
puts( "in settail" );
#endif
    CURSOR = HEAD->predecessor;
#ifdef DEBUG
printf( "cursor now at: %s %p\n", CURSOR->data, CURSOR );
#endif
    return list;
}

GList gforward( GList list )
{
    if ( HEAD == CURSOR )
        return list;
    else
    {
        CURSOR = CURSOR->successor;
        return list;
    }
}

GList gbackward( GList list )
{
    if ( HEAD == CURSOR )
        return list;
    else
    {
        CURSOR = CURSOR->predecessor;
        return list;
    }
}

GList ginsertbefore( GType data, GList list, Where where )
{
    Node  *previous = CURSOR->predecessor;
    Node  *node = NEW( Node, 1 );
    
    if ( node == NULL ) error( "in ginsertbefore: No space" );
    LENGTH++;
    node->data = data;
    node->successor = CURSOR;
    node->predecessor = previous;
    previous->successor = node;
    CURSOR->predecessor = node;
    if ( where == move ) CURSOR = node;
    return list;
}

GList ginsertafter( GType data, GList list, Where where )
{
    Node  *next = CURSOR->successor;
    Node  *node = NEW( Node, 1 );
    
#ifdef DEBUG
puts( "in ginsertafter" );
if (CURSOR != HEAD)
printf( "cursor now at: %s %p\n", CURSOR->data, CURSOR );
#endif
    if ( node == NULL ) error( "in ginsertafter: No space" );
    LENGTH++;
    node->data = data;
    node->successor = next;
    node->predecessor = CURSOR;
    next->predecessor = node;
    CURSOR->successor = node;
    if ( where == move ) CURSOR = node;
#ifdef DEBUG
printf( "inserted: %s\n", data );
printf( "cursor now at: %s %p\n", CURSOR->data, CURSOR );
#endif
    return list;
}

GList gremove( GList list, GDelete delete )
{
    Node  *previous = CURSOR->predecessor;
    Node  *next = CURSOR->successor;
    
    if ( HEAD == CURSOR ) return list;
    
    previous->successor = next;
    next->predecessor = previous;
    delete( CURSOR->data );
    free( CURSOR );
    CURSOR = next;
    LENGTH--;
    return list;
}

void gtraverse( GList list, GOperation operation )
{
    list = gsethead( list );
    while ( gisinlist( list ) )
    {
        operation( gcontent( list ) );
	list = gforward( list );
    }
}

GList gfind( GList list, GOperation2 operation, GType data )
/*
**  Returns NULL if data item could not be found.
*/
{
    list = gsethead( list );
    while ( gisinlist( list ) )
    {
	if ( operation( gcontent( list ), data ) )
	    return list;
	list = gforward( list );
    }
    return NULL;
}

GList gfindm( GList list, GOperationm operation, int item, char *mask )
/*
**  Returns NULL if data item could not be found.
*/
{
    list = gsethead( list );
    while ( gisinlist( list ) )
    {
	if ( operation( gcontent( list ), item, mask ) )
	    return list;
	list = gforward( list );
    }
    return NULL;
}

GList gfindnext( GList list, GOperation2 operation, GType data )
/*
**  Returns NULL if data item could not be found.
*/
{
    while ( gisinlist( list ) )
    {
	if ( operation( gcontent( list ), data ) )
	    return list;
	list = gforward( list );
    }
    return NULL;
}

GList gfindnextm( GList list, GOperationm operation, int item, char *mask )
/*
**  Returns NULL if data item could not be found.
*/
{
    while ( gisinlist( list ) )
    {
	if ( operation( gcontent( list ), item, mask ) )
	    return list;
	list = gforward( list );
    }
    return NULL;
}
